/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/
 */

class Solution {
    public String minWindow(String s, String t) {
        int[] hashT = new int[128], hashS = new int[128];
        char[] chS = s.toCharArray(), chT = t.toCharArray();
        int count = 0, n = t.length(), min = Integer.MAX_VALUE;
        int[] tmp = new int[2];
        tmp[0] = -1; tmp[1] = -1;

        for(char x : chT) {
            hashT[x]++;
        }

        for(int left = 0, right = 0; right < s.length(); right++) {
            // 1、进窗口
            hashS[chS[right]]++;
            // 维护有效字符个数
            if(hashS[chS[right]] <= hashT[chS[right]]) count++;
            
            // 2、判断
            while(count >= n) {
                // 3、更新结果
                if(right - left + 1 < min) {
                    min = right - left + 1;
                    tmp[0] = left;
                    tmp[1] = right;
                }
                // 出窗口前，维护有效字符count的个数
                if(hashS[chS[left]] <= hashT[chS[left]]) count--;
                // 出窗口
                hashS[chS[left]]--;
                left++;
            }
            
        }
        
        if(tmp[0] == -1 && tmp[1] == -1) return "";

        String ret = new String(s.substring(tmp[0], tmp[1] + 1));
        return ret;
    }
}